package algorithm.dynamic_planning.leetcode;

/**
 * @author yuisama
 * @date 2022/12/05 10:54
 **/
public class Num509_Fibo {
    //    // 自顶向下的备忘录思路
//    public int fib(int n) {
//        int[] memo = new int[n + 1];
//        return helper(n,memo);
//    }
//
//    private int helper(int n, int[] memo) {
//        // base case
//        if (n == 0 || n == 1) {
//            return n;
//        }
//        // 备忘录中有，直接返回该数字
//        if (memo[n] != 0) {
//            return memo[n];
//        }
//        memo[n] = helper(n - 1,memo) + helper(n - 2,memo);
//        return memo[n];
//    }
//    // 自底向上的动态转移方程
//    public int fib(int n) {
//        if(n == 0) return 0;
//        // f(n) = dp[n]
//        int[] dp = new int[n + 1];
//        dp[0] = 0;
//        dp[1] = 1;
//        for (int i = 2; i <= n; i++) {
//            dp[i] = dp[i - 1] + dp[i - 2];
//        }
//        return dp[n];
//    }
    // 状态压缩
    public int fib(int n) {
        if (n == 0) return 0;
        int last2 = 0,last1 = 1;
        int cur = 0;
        for (int i = 2; i <= n; i++) {
            cur = last1 + last2;
            last2 = last1;
            last1 = cur;
        }
        return last1;
    }
}